'''

给定一个数字，
我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11
翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。
请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
'''
import copy
mun = []
def dfs(num,alpha,index,res):
    #截止条件
    if index == len(num)-1:
        kk = copy.deepcopy(res)
        mun.append(kk)
        return
    for i in range(1,3):
        if index+1<len(num):
            substr = num[index+1:index+1+i]
            #筛选进入候选的节点
            if int(substr)<len(alpha) and (substr=="0" or not substr.startswith("0")):
                res.append(alpha[int(substr)])
                dfs(num,alpha,index+i,res)
                res.pop()#
if __name__ == '__main__':
    alpha = [chr(i) for i in range(97,123)]
    num = str(12258)
    res = []
    index = -1
    dfs(num,alpha,index,res)
    print(mun)